class Solution:
    def cuttingRope(self, n: int) -> int:
        # 数学推导，n等于3最优
        if n < 4:
            return n-1
        a, b = divmod(n, 3)
        if b == 0: return 3 ** a % 1000000007
        if b == 1: return 4 * 3 ** (a-1) % 1000000007
        return 2 * 3 ** (a-1) % 1000000007